package work.lianbiao;

import work.ListNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Problem142 {
//    public ListNode detectCycle(ListNode head) {
//        Set<ListNode> map = new HashSet<ListNode>();
//        ListNode node = head;
//        while (!map.contains(node)){
//            if (node==null||node.next==null){
//                return  null;
//            }
//            map.add(node);
//            node = node.next;
//        }
//        return node;
//    }

    //记结论 转一圈后 回到头再转一圈

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != slow) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = fast.next;
        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        Problem142 problem142 = new Problem142();
        problem142.detectCycle(node1);
    }

}
